/*public class Test {
}*/
import java.util.Arrays;

public class TSP {
    // 城市间距离矩阵（dist[i][j] 表示城市i到j的距离）
    private int[][] dist;
    // 城市数量
    private int n;
    // 最短路径长度（初始为无穷大）
    private int minDistance = Integer.MAX_VALUE;
    // 存储最短路径（城市索引序列）
    private int[] bestPath;

    public int[] solveTSP(int[][] dist) {
        this.dist = dist;
        this.n = dist.length;
        if (n == 0) return new int[0];

        // 路径数组：path[0] = 起点（固定为0），path[1..n-1] = 未访问城市
        int[] path = new int[n];
        path[0] = 0;
        // 访问状态：visited[0] = true（起点已访问）
        boolean[] visited = new boolean[n];
        visited[0] = true;

        // 回溯搜索（当前城市索引=0，已访问城市数=1，当前路径长度=0）
        backtrack(0, 1, 0, path, visited);
        return bestPath;
    }

    /**
     * 回溯函数：遍历所有可能的路径
     * @param curCity 当前所在城市索引
     * @param visitedCount 已访问的城市数量
     * @param currentDist 当前路径长度
     * @param path 当前路径（城市序列）
     * @param visited 访问状态数组
     */
    private void backtrack(int curCity, int visitedCount, int currentDist, int[] path, boolean[] visited) {
        // 剪枝：当前路径长度已超过现有最短路径，无需继续
        if (currentDist >= minDistance) {
            return;
        }

        // 终止条件：所有城市已访问，返回起点形成回路
        if (visitedCount == n) {
            // 加上回到起点的距离
            int totalDist = currentDist + dist[curCity][0];
            if (totalDist < minDistance) {
                minDistance = totalDist;
                bestPath = Arrays.copyOf(path, path.length);
            }
            return;
        }

        // 遍历所有未访问的城市，尝试前往
        for (int nextCity = 0; nextCity < n; nextCity++) {
            if (!visited[nextCity]) {
                // 选择：标记为已访问，更新路径和长度
                visited[nextCity] = true;
                path[visitedCount] = nextCity;
                // 递归：前往下一个城市
                backtrack(nextCity, visitedCount + 1, currentDist + dist[curCity][nextCity], path, visited);
                // 回溯：撤销选择
                visited[nextCity] = false;
            }
        }
    }

    // 测试用例
    public static void main(String[] args) {
        TSP tsp = new TSP();
        // 4个城市的距离矩阵（0-3为城市索引）
        int[][] dist = {
                {0, 10, 15, 20},
                {10, 0, 35, 25},
                {15, 35, 0, 30},
                {20, 25, 30, 0}
        };
        int[] bestPath = tsp.solveTSP(dist);
        System.out.println("TSP最短路径（城市索引序列）：" + Arrays.toString(bestPath));
        System.out.println("最短路径长度：" + tsp.minDistance); // 预期输出80（0→1→3→2→0）
    }
}